package 中等.贪心思想;

import java.util.Arrays;

/**
 * 给定两个大小相等的数组 nums1 和 nums2，nums1 相对于 nums2
 * 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
 * 返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/advantage-shuffle
 */
public class 优势洗牌_870 {

    public static void main(String[] args) {

        System.out.println(Arrays.toString(advantageCount(new int[]{12, 24, 8, 32}, new int[]{13, 25, 32, 11})));

    }

    /**
     * 贪心思想+二分查找+数组标记
     * <p>
     * 优先选择在nums1中 > nums2[i] 的最小元素
     * 如果没有，用 nums1 中最小元素填充
     */
    public static int[] advantageCount(int[] nums1, int[] nums2) {
        int[] ans = new int[nums1.length];
        boolean[] record = new boolean[nums1.length];

        Arrays.sort(nums1);

        for (int i = 0; i < ans.length; i++) {
            int targetIdx = -1;
            int left = 0, right = nums1.length - 1;
            int num2 = nums2[i];
            while (left <= right) {
                int mid = left + (right - left) / 2;
                // 注意：题目要求必须严格大于才算优势
                if (nums1[mid] > num2) {
                    targetIdx = mid;
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 找到 >= nums2[i] 的元素，但是不能重复使用，需要找到右边最近没有使用过的元素
            if (targetIdx != -1) {
                boolean hasBigNum = false;
                for (int r = targetIdx; r < record.length; r++) {
                    if (!record[r]) {
                        targetIdx = r;
                        record[r] = true;
                        hasBigNum = true;
                        break;
                    }
                }
                if (!hasBigNum) targetIdx = -1;
            }
            // 没有比 nums[i] 大的元素，用没有使用的最小元素填充
            if (targetIdx == -1) {
                for (int r = 0; r < record.length; r++) {
                    if (!record[r]) {
                        targetIdx = r;
                        record[r] = true;
                        break;
                    }
                }
            }

            ans[i] = nums1[targetIdx];
        }
        return ans;
    }

    // TODO 双指针

}
